package com.xzz.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: hhz
 * @create: 2021-12-22 09:42
 * 297. 二叉树的序列化与反序列化
 **/
public class Codec {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;
        String serialize = serialize(node1);
        System.out.println(serialize);
        System.out.println();
        TreeNode deserialize = deserialize("");
        System.out.println();

    }

    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
//        preSerialize(root,sb);
//        postSerialize(root,sb);
        levelSerialize(root,sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        LinkedList<String> list = new LinkedList<>(Arrays.asList(data.split(",")));
//        TreeNode treeNode = preDeserialize(list);
//        TreeNode treeNode = postDeserialize(list);
        TreeNode treeNode = levelDeserialize(list);
        return treeNode;
    }
    //前序遍历序列化
    public static void preSerialize(TreeNode root,StringBuilder sb) {
        if(root==null){
            sb.append("#,");
        }else {
            sb.append(root.val).append(",");
            preSerialize(root.left,sb);
            preSerialize(root.right,sb);
        }
    }
    //利用前序遍历反序列化
    public static TreeNode preDeserialize(LinkedList<String> nodes) {
        if(nodes.isEmpty()){
            return null;
        }
        //第一个元素就是root节点的值
        String first = nodes.removeFirst();
        if(first.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left =    preDeserialize(nodes);
        root.right = preDeserialize(nodes);
        return root;
    }

    //后序遍历序列化
    public static void postSerialize(TreeNode root,StringBuilder sb) {
        if(root==null){
            sb.append("#,");
        }else {
            postSerialize(root.left,sb);
            postSerialize(root.right,sb);
            sb.append(root.val).append(",");
        }
    }
    //利用后序遍历反序列化
    public static TreeNode postDeserialize(LinkedList<String> nodes) {
        if(nodes.isEmpty()){
            return null;
        }
        //最后一个元素就是root节点的值
        String last = nodes.removeLast();
        if(last.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(last));
        root.right = postDeserialize(nodes);
        root.left =  postDeserialize(nodes);
        return root;
    }

    //中序遍历可以序列化 但因难以确定root节点的位置 而无法反序列化

    //层级遍历序列化
    public static void levelSerialize(TreeNode root,StringBuilder sb) {
        if(root==null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            if(null==poll){
                sb.append("#,");
                continue;
            }else {
                sb.append(poll.val).append(",");
            }
            queue.add(poll.left);
            queue.add(poll.right);
        }
    }
    //利用层级遍历反序列化
    public static TreeNode levelDeserialize(LinkedList<String> nodes) {
        if(nodes.isEmpty()){
            return null;
        }
        if(nodes.getFirst().equals("")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(nodes.getFirst()));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        for (int i = 1; i < nodes.size();) {
            //队列中的都是根节点
            TreeNode poll = queue.poll();
            String left = nodes.get(i++);
            if(left.equals("#")){
                poll.left = null;
            }else {
                poll.left = new TreeNode(Integer.parseInt(left));
                queue.add(poll.left);
            }
            String right = nodes.get(i++);
            if(right.equals("#")){
                poll.right = null;
            }else {
                poll.right = new TreeNode(Integer.parseInt(right));
                queue.add(poll.right);
            }

        }
        return root;
    }
}
